package 力扣热题100;

import java.util.ArrayList;
import java.util.List;

public class LeetCode19 {
    List<List<Integer>> list=new ArrayList<>();
    List<Integer>list1=new ArrayList<>();//相当于一个临时的容器，如果满足就放把元素重新new一个容器放入list中，然后减少一个元素
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        dfs(candidates,target,0);
        return list;
    }

    private void dfs(int[] candidates, int target, int index) {
        if(index==candidates.length){//进行剪枝
            return;
        }
        if(target==0){
            list.add(new ArrayList<Integer>(list1));
            return;
        }
        dfs(candidates,target,index+1);
        if(target-candidates[index]>=0){
            list1.add(candidates[index]);
            dfs(candidates,target-candidates[index],index);
            list1.remove(list1.size()-1);
        }

    }
}
